package leetcode_二叉树;

import general_class.TreeNode;

/**
 * 验证二叉搜索树
 * 算法：二叉树
 *
 * @author yezh
 * @date 2023/1/7 17:41
 */
public class _98 {

    public boolean isValidBST_pre(TreeNode root) {
        return preOrder(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    boolean preOrder(TreeNode node, long left, long right) {
        if (node == null) return true;
        if (node.val <= left || node.val >= right) return false;
        if (!preOrder(node.left, left, node.val)) return false;
        return preOrder(node.right, node.val, right);
    }

    long preVal = Long.MIN_VALUE;

    public boolean isValidBST_in(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST_in(root.left)) return false;
        if (root.val <= preVal) return false;
        preVal = root.val;
        return isValidBST_in(root.right);
    }

    public boolean isValidBST_post(TreeNode root) {
        return postOrder(root)[1] != Long.MAX_VALUE;
    }

    long[] postOrder(TreeNode node) {
        // node.val <= left[1] || node.val >= right[0] 保证这个条件一定不成立
        if (node == null) return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        long[] left = postOrder(node.left);
        if (left[1] == Long.MAX_VALUE) return left;
        long[] right = postOrder(node.right);
        if (node.val <= left[1] || node.val >= right[0]) return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        return new long[]{Math.min(left[0], node.val), Math.max(right[1], node.val)};
    }

}
